package main.java.learning.directory.Work.数组.Tmt;

/**
 * @author: tianmingtai
 * @create: 2021/02/25 20:56
 * @description: 二分查找，给一个数组和一个关键数，查找后返回该数字的索引
 */

public class BinarySearchDay5 {
    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 50, 90, 31, 89, 31};
        learning.directory.Work.排序.Tmt.BubbleSortDay1.bubbleSort(arr);
        System.out.println(binarySearch(arr, 50));
    }

    public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;

        if (key < arr[left] || key > arr[right] || left >= right) {
            return -1;
        }
        while (left <= right) {
            int mid =  (right + left) / 2;
            if (arr[mid] > key) {
                // 中间的值比关键数字大，去左边
                right = mid - 1;
            } else if (arr[mid] < key) {
                // 中间值比关键字小，去右边查
                left = mid + 1;
            } else {
                return mid;
            }
        }
        // 一直没找到，返回-1
        return -1;
    }
}
